package com.study.leetcode;
//https://leetcode.cn/problems/maximum-sum-circular-subarray/
public class Solution_918 {
    /**
     * 解题思路如下：
     * 分成两种情况
     * 1.无环取子序列最大值和
     * 2.考虑环的情况则相当于要找到一个最小的子序列和使得sum(nums) - sum(mins)最大
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular(int[] nums) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int curMax = 0;
        int curMin = 0;
        int sum = 0;
        for (int num : nums) {
            curMax = curMax > 0 ? curMax + num : num;
            max = curMax > max ? curMax : max;
            curMin = curMin < 0 ? curMin + num : num;
            min = curMin < min ? curMin : min;
            sum += num;
        }
        if (max < 0) {
            return max;
        }
        return Math.max(sum - min, max);
    }

    public static void main(String[] args) {

    }
}
